import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 17.11. 单词距离
 * https://leetcode-cn.com/problems/find-closest-lcci/
 */
public class Solutions_mianshi_17_11 {
    public static void main(String[] args) {
        String[] words = {"I", "am", "a", "student", "from", "a", "university", "in", "a", "city"};
        String word1 = "a", word2 = "student";  // output: 1

        int result = findClosest(words, word1, word2);
        System.out.println(result);
    }

    /**
     * 解法二：线性扫描 + 双指针（11ms）
     */
    public static int findClosest(String[] words, String word1, String word2) {
        int res = words.length + 1, idx1 = -1, idx2 = -1;

        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                idx1 = i;
            } else if (words[i].equals(word2)) {
                idx2 = i;
            } else {
                continue;
            }
            if (idx1 > -1 && idx2 > -1) {
                // 两个字符串都出现了，比较距离
                res = Math.min(res, Math.abs(idx1 - idx2));
            }
            if (res == 1) {
                // 提前返回，最短距离只能是 1
                return res;
            }
        }
        return res;
    }

    /**
     * 解法一：list + 双指针（13ms）
     */
    public static int findClosest2(String[] words, String word1, String word2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        int res = words.length + 1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                list1.add(i);
            } else if (words[i].equals(word2)) {
                list2.add(i);
            }
        }
        int idx1 = 0, idx2 = 0, len1 = list1.size(), len2 = list2.size();
        while (idx1 < len1 && idx2 < len2) {
            int m = list1.get(idx1);
            int n = list2.get(idx2);
            res = Math.min(res, Math.abs(m - n));
            if (res == 1) {
                // 提前返回，最短距离只能是 1
                return res;
            }
            // 双指针移动
            // a：2  5  8
            // b：3  6
            if (m < n) {
                idx1 ++;
            } else {
                idx2 ++;
            }
        }
        return res;
    }
}
